 function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} 
function reConstructBinaryTree(pre, vin)
{
    // write code here
    // 需要在中序序列当中找到根节点在中序序列中的下标
    // var dic = {} // 构建一个字典 键是数字 对应的值是下标 这样做的好处是 可以通过这个值 来找到这个值所对应的下标
    // for(let i of vin){
    //   dic[i] = vin.indexOf(i) // 字典的键是这个数字 对应的值是这个数字的下标 
    // }
    // 定义一个递归的函数 需要的参数是 前序遍历序列中根节点的位置,以及在中序遍历中左右两个边界
    // preRootId 前序序列中根节点的位置
    // inl inr 这个子树的中序遍历中的左右边界
    function construct(preRootId,inL,inR){
      // 递归的出口 就是中序序列的左右边界 如果左边界 大于 有边界 就返回空节点
      if(inL > inR) return null
      var rootVal = pre[preRootId] // 由前序序列中根节点的位置 找到根节点的值
      // 中序序列中根节点的下标值 通过字典就可以找到
      var inRootId = vin.indexOf(rootVal) // 中序遍历中根节点的下标值 那我直接使用 vin.indefOf(rootVal)
      // var inRootId = dic[rootVal] // 中序遍历中根节点的下标值 那我直接使用 vin.indefOf(rootVal)
      // 找到根节点后的下标值 很容易就得到他的左右子树的内容
      var leftSize = inRootId - inL // 左子树的大小 就是根节点的下标 - 左边界
      // 有了这个东西我们就可以递归的构造二叉树
      // 首先是根节点
      var root = new TreeNode(rootVal) // 根节点就用根节点的值构造
      root.left = construct(preRootId+1,inL,inRootId-1) // 下面是左子树 在构造左子树的过程中需要的根节点的位置 需要在原有的根节点的在前序序列中的位置 向后移动一位  中序遍历中左边界是不变的 右边界是中序遍历的下标-1 边界用的都是闭区间
      // 下面构造右子树 右子树的根节点是需要在原有的位置上 向后移动 移动的位置的个数是 左子树的大小
      root.right = construct(preRootId+leftSize+1,inRootId+1,inR)
      return root // 最后返回根节点
    }
    return construct(0,0,vin.length-1)
}

module.exports = {
    reConstructBinaryTree : reConstructBinaryTree
};